我的Bilibili频道：香芋派Taro
我的个人博客：taropie0224.github.io（阅读体验更佳）
我的公众号：香芋派的烘焙坊
我的音频技术交流群：1136403177
我的个人微信：JazzyTaroPie

https://leetcode.cn/problems/next-permutation/

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        int i = nums.size() - 2; //初始化i为倒数第二个元素的index
        //从后往前扫描，如果相邻的两个元素，前一个大于后一个，则i--，直到找到那个升序的（从左往右）
        while (i >= 0 && nums[i] >= nums[i + 1]) { 
            i--;
        }
        //如果找到了（没找到的话i为-1）
        if (i >= 0) {
            int j = nums.size() - 1; //初始化j为最后一个元素的index
            //从后往前扫描，直到遇到比i处小的数
            while (j >= 0 && nums[i] >= nums[j]) {
                j--;
            }
            //交换i和j位置处的元素
            swap(nums[i], nums[j]);
        }
        //反转位置i后的所有元素
        reverse(nums.begin() + i + 1, nums.end());
    }
};